Global routing has long been a requirement in the Integrated Circuit (IC) realm. Without global routing, the immense number of connections in a modern IC would make it nearly impossible to auto-route an IC in a reasonable amount of time. However, no one has ever successfully created a global routing solution for Printed Circuit Board (PCB) technology.
The most limiting aspect of an auto-routing system is its representation of routing space. In current systems, routing space is represented as a collection of interconnected regions. These regions can be either the objects to avoid or the areas still available for routing or both. The representation of the routing space selected also defines and limits the ability of the router to find via locations.
Historically, the earliest auto-routers represented the entire routing area using squares. Some of the squares were marked as “used”; the others were marked as “available”. These auto-routing systems used a fixed routing grid, making each of these squares the same size. This made finding potential via locations relatively simple since the corresponding location on another layer was on the corresponding location in the other layer's array of squares.
Use of squares resulted in much of the space being unusable, because not all the features on a circuit have the same width. Over time, many variations were developed to allow the areas to be modified to arrays of rectangles. This was accomplished using several different techniques, including varying the grid over a region and repeating a pattern of grids, among others. Mapping a location from one layer to another was slightly more complicated, but still mathematically simple. As simple as it may seem, moving from using an array of squares to using an array of rectangles was a significant advance in auto-routing. Using an array of rectangles maintained the processing speed possible with using squares, but allowed more usable space in the system. In the IC realm, variations on this process are still the norm.
As PCB devices began to use more closely spaced components and as surface mount devices became more common, it became impossible to find a grid or any variation on a grid that would allow the system to work. Newer auto-routing systems are “gridless”. That is, the rectangles which the system defines can be any size. A rectangle no longer needed to be the same size as its neighbors. It no longer needed to have exactly four neighbors (north, south, east and west). However in these systems, routing space is still represented by rectangles.
Finding potential via locations with arbitrary rectangles in such systems is now much more complicated, since it is not trivial to determine which rectangles on one layer overlap with which rectangles on another layer. The intersection of any two rectangles has three possibilities: 1) the intersection can be a rectangle, 2) the two rectangles might touch (at a point or a line segment) but not overlap, or 3) they do not intersect at all. Storing the rectangles in a searchable database (such as a quad-tree or sector-map) make it possible to develop algorithms to make this calculation speed acceptable.
Modernly, a few auto-routing systems have used “octolinear octagons.” That is, an 8-sided polygon whose sides are at 0, 45, 90, 135, 180, 225, 270 and 315 degrees. This has the advantage that it represents 45-degree routing well and can be stored compactly. And, a rectangle can be considered as a degenerate octolinear octagon. That is, the four diagonal sides of the octolinear octagon have zero length.
The intersection of two arbitrary octagons can be a very complex shape. But, the intersection of two octolinear octagons is always an octolinear octagon, possibly degenerate with one or more zero length sides. There are mathematical optimizations existing that allow this computation to be reasonably efficient.
The only other object shape to have been tried in an autorouter is a triangle. Using triangles has the obvious advantage that any shape can be approximated with triangles. However, it has a severe disadvantage in that the intersection of two triangles is not necessarily a triangle. In fact, the intersection can be a 3, 4, 5, or 6 sided polygon.
An IC router uses global information to create routing at the next lower level; it normally will insert vias to resolve crossovers. In PCB routing, this is not practical. The radius of a PCB via is usually much larger than wires; it often penetrates many layers. And, in many cases, signal integrity requirements severely limit the numbers of vias on a net. So, in PCB, insertion of a via is a very “expensive” operation that must be used very sparingly if a complete solution is to be reached. Adding two vias to resolve a single crossover is almost never acceptable. As a result, traditional methods have been unable to use global information for detail routing on a PCB.
To date, every PCB auto-routing system that has ever attempted to use triangles for its representation of space has encountered problems finding via locations. What is needed is an auto-routing system and method that can efficiently and effectively utilize triangular space representations.